1. Technical Field
The present invention relates to an improved data processing system. In particular, the present invention relates to loop optimization transformation in software applications. Still more particularly, the present invention relates to reducing memory access latency and number of computations in a program using automatic second-order predictive commoning.
2. Description of Related Art
A compiler is a program that executes in a data processing system, which translates a high-level language program into a functionally equivalent low-level language program, such as machine language instructions. In the process of compilation, the compiler optimizes the source program by generating an explicit intermediate representation and performing code optimization.
Currently, most well-known code optimization techniques are designed towards reducing memory access latency. Memory access latency is often caused by reading from or writing to a large number of memory addresses during iterations of program loops. Memory access latency causes the processor to stall until required data is retrieved from memory.
In some applications, such as stencil algorithms that are used to iteratively solve partial differential equations, memory elements retrieved in an iteration of a loop may also be required in one or more immediate subsequent iterations of the loop. Such application requires the same elements to be retrieved from memory or cache repeatedly until they are no longer needed.
As mentioned in patent application entitled “Optimizing Source Code for Iterative Execution”, filed on Dec. 19, 2001, U.S. application Ser. No. 10/314,094, herein incorporated by reference, predictive commoning is a loop optimization transformation technique that identifies access to memory elements that are required in immediate subsequent iterations. By identifying these elements, storing the content of these elements in registers, and using the registers in subsequent iterations, many redundant memory accesses are saved. In addition, predictive commoning may also unroll a transformed loop, such that software register renaming can be applied. Software register renaming is applied to avoid the need to copy values between registers.
Second-order predictive commoning is a more complex loop optimization transformation technique that identifies sub-expressions and combinable sub-expressions. The results of the computation of sub-expressions or combination sub-expressions can be reused in immediate subsequent iterations, such that not only the number of memory accesses is reduced, computations, such as multiplications, additions, function calls with no side effects, may be saved.
Three-dimensional stencil programs, such as subroutine “psinv” and “resid” in mgrid from the SPEC2000 benchmark, include opportunities for second-order predictive commoning to save computations of combinable sub-expressions. These sub-expressions carry the combined sum of certain memory elements over to the next iteration. Instead of storing and retrieving separate references to and from registers, only sums of combined sub-expressions are stored in registers. In this way, not only is the number of memory accesses reduced, the number of operations required is also reduced. When the number of operations is reduced, performance of the program is also improved
However, existing solutions, including TOBEY, a compiler product available from International Business Machines Corporation, are limited to analysis of first-order predictive commoning, which handles strictly single memory references. Therefore, it would be advantageous to have a method and apparatus that automatically analyzes the intermediate representation of a program code to identify opportunities of second-order predictive commoning and perform necessary transformations for optimization.